package vernhe;

import java.util.Comparator;

public class BinarySearchTree<E> extends BinaryTree<E>{

    private Comparator<E> comparetor;

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(Comparator<E> comparetor) {
        this.comparetor = comparetor;
    }

    public void add(E element) {
        elementNotNullCheck(element);

        //如果是第一个元素，即根节点为null
        if (root == null) {
            root = new Node<>(element,null);
            size++;
            return;
        }

        //逐个进行比较
        Node<E> node = root;
        Node<E> parent = null;
        int cmp = 0;
        while (node != null) {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            }else if (cmp < 0) {
                node = node.left;
            }else {
                //相等
                node.element = element;
                return;
            }
        }

        //判断是父节点的左边还是右边
        Node<E> newNode = new Node<>(element,parent);
        if (cmp > 0) {
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }

    }

    /**
     * 两个节点进行比较
     * @param e1
     * @param e2
     * @return  0表示相等，> 表示e1大，< 表示e2大
     */
    private int compare(E e1,E e2) {
        /**
         * 这样写的好处就是不用要求保存的对象一定要实现comparable方法，
         * 而是又外部自行决定使用比较器还是实现comparable方法
         */
        //有比较器用比较器
        if (comparetor != null) {
            return comparetor.compare(e1,e2);
        }
        //没有比较器就用实现Comparable的compareTo方法
        return ((Comparable<E>)e1).compareTo(e2);
    }

    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    public void remove(E element) {
        remove(node(element));
    }

    /**
     * 根据元素查找节点
     * @param element
     * @return
     */
    private Node<E> node(E element) {
        if (root == null) return null;
        Node<E> node = root;
        while (node != null) {
            int cmp = compare(element,node.element);
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0){
                node = node.left;
            } else {
                //找到就返回
                return node;
            }
        }
        //没找到返回空
        return null;
    }

    private void remove(Node<E> node) {
        if (node == null) return;
        size--;

        //判断是否是度为2的节点
        if (node.hasTowChildren()) {
            //得到替代被删除节点的前驱节点或者后继节点
            Node<E> s = successor(node);
            //覆盖被删除节点的值
            node.element = s.element;
            //删除前驱节点，（本方法就是要删除node节点，因为采用的覆盖的方式，所以真正被删除的节点一定是度为1或者0的节点）
            node = s;
        }

        //如果是度为1的节点，replacement必然不为空，度为0则为空
        Node<E> replacement = node.left != null ? node.left : node.right;
        if (replacement != null) {
            //就算node是根节点，即node.parent == null 也适用
            replacement.parent = node.parent;
            //判断是否为根节点
            if (node.parent == null) {
                root = replacement;
            } else if (node == node.parent.left) {
                //修改原先指向被删除元素的指针
                node.parent.left = replacement;
            } else {
                node.parent.right = replacement;
            }
        } else if (node.parent == null) {
            //度为0是根节点的时候
            root = null;
        } else {
            //度为0是叶子节点的时候
            //根据左右两种情况来进行删除
            if (node == node.parent.left) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
        }
    }

    public boolean contains(E element) {
        return node(element) != null;
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (root == null) return "";
        return toString(root,sb,"");
    }

    private String toString(Node<E> node,StringBuilder sb,String perfix) {
        if (node.left != null) toString(node.left,sb,perfix + "[L]");
        sb.append(perfix).append("【").append(node.element).append("】").append("\n");
        if (node.right != null) toString(node.right,sb,perfix + "[R]");
        return sb.toString();
    }
}
